package com.c2b.algorithm.leetcode.base.backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * <a href='https://leetcode.cn/problems/letter-case-permutation/description/'>字母大小写全排列(Letter Case Permutation)</a>
 * <p>给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。</p>
 * <p>返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：s = "a1b2"
 *      输出：["a1b2", "a1B2", "A1b2", "A1B2"]
 *
 * 示例 2:
 *      输入: s = "3z4"
 *      输出: ["3z4","3Z4"]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>1 <= s.length <= 12</li>
 *         <li>s 由小写英文字母、大写英文字母和数字组成</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/10/26 16:51
 */
public class LC0784LetterCasePermutation_M {

    static class Solution {
        public List<String> letterCasePermutation(String s) {
            List<String> retList = new ArrayList<>();
            dfs(s.toLowerCase().toCharArray(),0,"",retList);
            return retList;
        }

        private void dfs(char[] chars, int startPoint,String path, List<String> retList) {
            if (startPoint == chars.length) {
                retList.add(path);
                return;
            }
            if (Character.isDigit(chars[startPoint])) {
                // 如果是数字
                path += chars[startPoint];
                dfs(chars, startPoint + 1, path, retList);
            } else {
                // 如果是字母。因为是都转成小写了，直接先处理小写，再处理大写
                path += chars[startPoint];
                dfs(chars, startPoint + 1, path, retList);
                path = path.substring(0, path.length() - 1);
                path += (char) (chars[startPoint] - 32);
                dfs(chars, startPoint + 1, path, retList);
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        for (String str :solution.letterCasePermutation("1b2") ) {
            System.out.println(str);
        }
    }
}
